package tree;

/**
 * 排序二叉树
 */
public class BinaryTree<E extends Comparable<E>> {
    //root存放根节点的引用
    private Node root;

    class Node {
        /**
         * 描述二叉树中的某个节点
         * 其中,data用于存放元素
         * left和right 用于存放左右子树的引用
         */
        E data;
        Node right;
        Node left;

        Node(E e) {
            data = e;
        }

        boolean append(E e){
            if (data.compareTo(e)==0){
                return false;
            }
            if (data.compareTo(e)>0){
                if (left==null) {
                    left = new Node(e);
                    return true;
                }else{
                    return left.append(e);
                }
            }else {
                if (right==null){
                    right = new Node(e);
                    return true;
                }else{
                    return right.append(e);
                }
            }
        }


        public void toString(StringBuilder sb) {
                if (left !=null){
                    left.toString(sb);
                }
                sb.append(data).append(", ");
                if (right != null){
                    right.toString(sb);
                }
        }

        }

    @Override
    public String toString() {
        if (root == null){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        root.toString(sb);
        sb.delete(sb.length()-1,sb.length());
        sb.append("]");
        return sb.toString();

    }
    boolean add(E e){
        if (root==null){
            root = new Node(e);
            return true;
        }
        return root.append(e);
    }
}

//中 左中右
//先 中左右
//后 左右中


